#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "abb.h"
#include "pila.h"

typedef struct abb_nodo{
	char* clave;
	void* dato;
	struct abb_nodo* hizq;
	struct abb_nodo* hder;
}abb_nodo_t;

struct abb{
	abb_comparar_clave_t cmp;
	abb_nodo_t* raiz;
	size_t cantidad;
	abb_destruir_dato_t destruir_dato;
};

struct abb_iter{
	pila_t* pila;
};

static abb_nodo_t* crear_nodo(const char* clave, void* dato){
	abb_nodo_t* nodo_nuevo = (abb_nodo_t*)malloc(sizeof(abb_nodo_t));
	if(nodo_nuevo==NULL) return NULL;
	nodo_nuevo->hizq = NULL;
	nodo_nuevo->hder = NULL;
	nodo_nuevo->dato = dato;
	char* copia_clave = (char*)malloc(sizeof(char) * (strlen(clave)+1));
	if(copia_clave == NULL){
		free(nodo_nuevo);
		return NULL;
	}
	strcpy(copia_clave,clave);
	nodo_nuevo->clave = copia_clave;
	return nodo_nuevo;
}

static void destruir_nodo(abb_nodo_t* nodo){
	free(nodo->clave);
	free(nodo);
}

abb_t* abb_crear(abb_comparar_clave_t cmp, abb_destruir_dato_t destruir_dato){
	abb_t* arbol = (abb_t*)malloc(sizeof(abb_t));
	if (arbol==NULL) return NULL;
	arbol->cmp = cmp;
	arbol->destruir_dato = destruir_dato;
	arbol->raiz = NULL;
	arbol->cantidad = 0;
	return arbol;
}

static bool abb_guardar_recursiva(abb_nodo_t** nodo,const char *clave, void *dato,abb_t* arbol){
	if((*nodo)==NULL){
		(*nodo) = crear_nodo(clave,dato);
		if((*nodo)==NULL) return false;
		arbol->cantidad ++;
		return true;
	}
	int r =arbol->cmp(clave,(*nodo)->clave);
	if(r==0){
		if(arbol->destruir_dato!=NULL) arbol->destruir_dato((*nodo)->dato);
		(*nodo)->dato = dato;
		return true;
	}
	if(r<0) return abb_guardar_recursiva(&((*nodo)->hizq),clave,dato,arbol);
	return abb_guardar_recursiva(&((*nodo)->hder),clave,dato,arbol);
}

bool abb_guardar(abb_t *arbol, const char *clave, void *dato){	
	if (abb_guardar_recursiva(&arbol->raiz,clave,dato,arbol)) return true;
	return false;
}

static abb_nodo_t* buscar_menor(abb_nodo_t* nodo){
	if(nodo->hizq == NULL) return nodo;
	return buscar_menor(nodo->hizq);
}

static bool reemplazar_nodo(abb_nodo_t* nodo1,abb_nodo_t* nodo2){
	char* copia_clave = (char*)malloc(sizeof(char) * (strlen(nodo2->clave)+1));
	if(copia_clave == NULL) return false;
	strcpy(copia_clave,nodo2->clave);
	free(nodo1->clave);
	nodo1->clave = copia_clave;
	nodo1->dato = nodo2->dato;
	return true;
}

static void *abb_borrar_recursiva(abb_nodo_t** nodo,const char *clave,abb_t *arbol){
	if((*nodo)==NULL) return NULL;
	int r = arbol->cmp(clave,(*nodo)->clave);
	if (r==0){
		void* dato_borrado = (*nodo)->dato;
		if((*nodo)->hizq == NULL && (*nodo)->hder == NULL){
			destruir_nodo((*nodo));
			arbol->cantidad --;
			(*nodo) = NULL;
			return dato_borrado;
		}
		if ((*nodo)->hizq == NULL){
			abb_nodo_t* aux = (*nodo)->hder;
			destruir_nodo((*nodo));
			(*nodo) = aux;
			arbol->cantidad --;
			return dato_borrado;
		}
		if ((*nodo)->hder == NULL){
			 abb_nodo_t* aux = (*nodo)->hizq;
			 destruir_nodo((*nodo));
			 (*nodo) = aux;
			 arbol->cantidad --;
			 return dato_borrado;
		}
		abb_nodo_t* menor_derecha = buscar_menor((*nodo)->hder);
		if(!reemplazar_nodo((*nodo),menor_derecha)) return NULL;
		abb_borrar_recursiva(&(*nodo)->hder,menor_derecha->clave,arbol);
		return dato_borrado;	
	}
	if(r<0) return abb_borrar_recursiva(&((*nodo)->hizq),clave,arbol);
	return abb_borrar_recursiva(&((*nodo)->hder),clave,arbol);
}

void *abb_borrar(abb_t *arbol, const char *clave){
	return abb_borrar_recursiva(&(arbol->raiz),clave,arbol);
}

static void *abb_obtener_recursiva(abb_nodo_t* nodo,const char *clave,const abb_t *arbol){
	if (nodo==NULL) return NULL;
	int r = arbol->cmp(clave,nodo->clave);
	if(r==0) return nodo->dato;
	if(r<0) return abb_obtener_recursiva(nodo->hizq,clave,arbol);
	return abb_obtener_recursiva(nodo->hder,clave,arbol);
}

void *abb_obtener(const abb_t *arbol, const char *clave){
	return abb_obtener_recursiva(arbol->raiz,clave,arbol);	
}

static bool abb_pertenece_recursiva(abb_nodo_t* nodo,const char *clave,const abb_t *arbol){
	if(nodo==NULL) return false;
	int r = arbol->cmp(clave,nodo->clave);
	if(r==0) return true;
	if(r<0) return  abb_pertenece_recursiva(nodo->hizq,clave,arbol);
	return abb_pertenece_recursiva(nodo->hder,clave,arbol);
}

bool abb_pertenece(const abb_t *arbol, const char *clave){
	return abb_pertenece_recursiva(arbol->raiz,clave,arbol);
}

size_t abb_cantidad(abb_t *arbol){
	return arbol->cantidad;
}

static void abb_destruir_recursiva(abb_nodo_t* nodo,abb_t* arbol){
	if(nodo==NULL) return;
	abb_destruir_recursiva(nodo->hizq,arbol);
	abb_destruir_recursiva(nodo->hder,arbol);
	if(arbol->destruir_dato != NULL) arbol->destruir_dato(nodo->dato);
	destruir_nodo(nodo);
	return;	
}

void abb_destruir(abb_t *arbol){
	abb_destruir_recursiva(arbol->raiz,arbol);
	free(arbol);
}

void abb_in_order_recursiva(abb_nodo_t* nodo, bool funcion(const char *, void *, void *), void *extra){
	if(nodo==NULL) return;
	abb_in_order_recursiva(nodo->hizq,funcion,extra);
	funcion(nodo->clave,nodo->dato,extra);
	abb_in_order_recursiva(nodo->hder,funcion,extra);
	return;
}

void abb_in_order(abb_t *arbol, bool funcion(const char *, void *, void *), void *extra){
	abb_in_order_recursiva(arbol->raiz,funcion,extra);
	return;
}

static bool apilo_con_sus_hijos_izquierdos(abb_nodo_t* nodo,pila_t* pila){
	if(nodo==NULL) return true;
	if(!pila_apilar(pila,nodo)) return false;
	if(!apilo_con_sus_hijos_izquierdos(nodo->hizq,pila)) return false;
	return true;
}

abb_iter_t *abb_iter_in_crear(const abb_t *arbol){
	abb_iter_t* iter = (abb_iter_t*)malloc(sizeof(abb_iter_t));
	if(iter==NULL) return NULL;
	iter->pila = pila_crear();
	if(iter->pila==NULL){
			free(iter);
			return NULL;
	}
	if(!apilo_con_sus_hijos_izquierdos(arbol->raiz,iter->pila)){
			abb_iter_in_destruir(iter);
			return NULL;
	};
	return iter;
}

bool abb_iter_in_avanzar(abb_iter_t *iter){
	abb_nodo_t* aux = (abb_nodo_t*)pila_desapilar(iter->pila);
	if (aux==NULL) return false;
	if(!apilo_con_sus_hijos_izquierdos(aux->hder,iter->pila)) return false;	
	return true;
}

const char *abb_iter_in_ver_actual(const abb_iter_t *iter){
	abb_nodo_t* actual = (abb_nodo_t*)pila_ver_tope(iter->pila);
	if(actual==NULL) return NULL;
	return actual->clave;
}

bool abb_iter_in_al_final(const abb_iter_t *iter){
	return pila_esta_vacia(iter->pila);
}

void abb_iter_in_destruir(abb_iter_t* iter){
	pila_destruir(iter->pila);
	free(iter);
}
